#include <cstdio>
#include <cstring>
const int mod=1000000009;
int n,ans=0;
int f[2][10][11];
bool p[1000];
int main()
{
   // freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    scanf("%d\n",&n);
    int i,j,k,x;
    memset(p,1,sizeof(p));
    p[0]=p[1]=false;
    for (i=2;i<=999;i++)
      if (p[i]) for (j=i+i;j<=999;j=j+i) p[j]=false;
    memset(f,0,sizeof(0));
    for (i=1;i<=9;i++)
      for (j=0;j<=9;j++)
        for (k=0;k<=9;k++)
          if (p[i*100+j*10+k]) f[1][i][j]++;
    for (x=4;x<=n;x++)
      for (i=1;i<=9;i++)
        for (j=1;j<=9;++j)
        {
            f[x&1][i][j]=0;
            for (k=(x>4)?1:0;k<=9;k++)
              if (p[i*100+j*10+k]) f[x&1][i][j]=(f[x&1][i][j]+f[(x-1)&1][j][k])%mod;
            //printf("f[%d][%d][%d]=%d\n",x,i,j,f[x&1][i][j]);
        }
    for (i=1;i<=9;i++)
      for (j=(n>3)?1:0;j<=9;j++)
        ans=(ans+f[n&1][i][j])%mod;
    printf("%d\n",ans);
    return 0;
}
